package greedy;

/**
 * @Author: 海琳琦
 * @Date: 2022/2/28 11:01
 * https://leetcode-cn.com/problems/lemonade-change/
 */
public class LemonadeChange {

    /**
     * 所以局部最优：遇到账单20，优先消耗美元10，完成本次找零。全局最优：完成全部账单的找零。
     * @param bills
     * @return
     */
    public static boolean lemonadeChange(int[] bills) {
        int money5 = 0, money10 = 0;
        for (int i = 0; i < bills.length; i++) {
            if (bills[i] == 5) {
                money5++;
            } else if (bills[i] == 10) {
                if (money5 < 0) {
                    return false;
                }
                money5--;
                money10++;
            } else {
                //20  /10 5
                if (money10 > 0 && money5 > 0) {
                    money10--;
                    money5--;
                } else if (money5 >= 3) {
                    money5 -= 3;
                } else {
                    return false;
                }
            }
        }
        return true;
    }

    public static void main(String[] args) {
        int[] a = {5,5,5,10,5,5,10,20,20,20};
        boolean b = lemonadeChange(a);
        System.out.println();
    }
}
